package leetcode.editor.cn.dsa14_greedyAlgorithm;
//在一排多米诺骨牌中，A[i] 和 B[i] 分别代表第 i 个多米诺骨牌的上半部分和下半部分。
// （一个多米诺是两个从 1 到 6 的数字同列平铺形成的 ——该平铺的每一半上都有一个数字。）
// 我们可以旋转第 i 张多米诺，使得 A[i] 和 B[i] 的值交换。
// 返回能使 A 中所有值或者 B 中所有值都相同的最小旋转次数。
// 如果无法做到，返回 -1.

import java.util.Random;

public class MinimumDominoRotationsForEqualRow1007_2 {
    public static void main(String[] args) {
        MinimumDominoRotationsForEqualRow1007_1.Solution solution = new MinimumDominoRotationsForEqualRow1007_1().new Solution();
        int[] arr1 = {2,1,2,4,2,2}, arr2 = {5,2,6,2,3,2};
        System.out.println(solution.minDominoRotations(arr1, arr2)); //2
        int[] arr3 = {3,5,1,2,3}, arr4 = {3,6,3,3,4};
        System.out.println(solution.minDominoRotations(arr3, arr4)); //-1
        int[] arr5 = {1,1,1,1}, arr6 = {1,2,6,1};
        System.out.println(solution.minDominoRotations(arr5, arr6)); //0
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int minDominoRotations(int[] A, int[] B) {
            // 使用循环在leetcode上能达到击败100%，但实际效率不如前一种
            int n = A.length;
            int ret=-1;
            for (int i = 1; i <= 6; i++) {
                int rotations = check(i, A, B, n);
                if (ret == -1) {
                    ret = rotations;
                } else if (rotations != -1) {
                    ret = Math.min(rotations, ret);
                }
            }
            return ret;
        }
        // 检查将A或者B中元素全部变成x需要多少次旋转
        public int check(int x, int[] A, int[] B, int n) {
            //定义两个计数器，分别统计将A中/B中元素变成x需要多少次旋转
            int rotationsA = 0, rotationsB = 0;
            // 遍历骨牌判断是否能完成任务（在A中完成或者在B中完成）
            for (int i = 0; i < n; i++) {
                // 如果当前多米诺骨牌上没有数字x，那么不可能完成任务
                if (A[i] != x && B[i] != x) return -1;
                    // 如果当前多米诺骨牌上A[i]不是x，那么A需要旋转一次
                else if (A[i] != x) rotationsA++;
                    // 如果当前多米诺骨牌上B[i]不是x，那么B需要旋转一次
                else if (B[i] != x) rotationsB++;
            }
            // 返回最小旋转次数
            return Math.min(rotationsA, rotationsB);
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)
}